package org.example.leetCode;

/**
 * 474. 一和零
 * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
 * 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
 * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
 */
public class Code474 {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (String str : strs) {
            int x = 0, y = 0, index = 0;
            while (index < str.length()) {
                if (str.charAt(index++) == '0') {
                    x++;
                } else {
                    y++;
                }
            }
            for (int p = m; p >= x; p--) {
                for (int j = n; j >= y; j--) {
                    dp[p][j] = Math.max(dp[p - x][j - y] + 1, dp[p][j]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Code474 solution = new Code474();

        // 测试用例1
        String[] strs1 = {"10", "0001", "111001", "1", "0"};
        int m1 = 5, n1 = 3;
        int result1 = solution.findMaxForm(strs1, m1, n1);
        System.out.println("测试用例1:");
        System.out.println("输入: strs = [\"10\",\"0001\",\"111001\",\"1\",\"0\"], m = 5, n = 3");
        System.out.println("输出: " + result1);
        System.out.println("预期: 4");
        System.out.println();

        // 测试用例2
        String[] strs2 = {"10", "0", "1"};
        int m2 = 1, n2 = 1;
        int result2 = solution.findMaxForm(strs2, m2, n2);
        System.out.println("测试用例2:");
        System.out.println("输入: strs = [\"10\",\"0\",\"1\"], m = 1, n = 1");
        System.out.println("输出: " + result2);
        System.out.println("预期: 2");
        System.out.println();

        // 测试用例3
        String[] strs3 = {"10", "0001", "111001", "1", "0"};
        int m3 = 4, n3 = 3;
        int result3 = solution.findMaxForm(strs3, m3, n3);
        System.out.println("测试用例3:");
        System.out.println("输入: strs = [\"10\",\"0001\",\"111001\",\"1\",\"0\"], m = 4, n = 3");
        System.out.println("输出: " + result3);
        System.out.println("预期: 3");
    }

}
